//归并排序
#include<cpp.h>
using namespace std;
typedef vector<int> ve; 
const int maxn = 100;
ve ret;  
void merge(ve& a, int begin, int mid, int end)
{
	int b[maxn] = { 0 };
	int l = begin;
	int r = mid + 1;
	int k = 0;
	while (l <= mid && r <= end)
	{
		if (a[l] > a[r])
			b[k++] = a[l], ret[l] += end - r + 1,l++;
		else
			b[k++] = a[r++];
	}
	while (l <= mid)b[k++] = a[l++];
	while (r <= end)b[k++] = a[r++];
	k = 0;  
	for (int i = begin; i <= end; i++)
	{
		a[i] = b[k++];      
	}
}

void mergesort(ve& a, int begin, int end)
{
	if (begin >= end)return;
	int mid = (begin + end) >> 1;
	mergesort(a, begin, mid);
	mergesort(a, mid + 1, end); 
	merge(a, begin, mid,end);   
}

class Solution {
public:
	ve countSmaller(ve& a)
	{
		ret.resize(a.size());
		mergesort(a, 0, a.size() - 1);
		return ret;
	}
};


int main()
{
	ve a{ -1 };
	Solution  m;
	m.countSmaller(a); 

	return 0;
}
